import java.util.*;

public class Codec {
    public static class TreeNode {
        int val;
         TreeNode left;
         TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public String serialize(TreeNode root){
        if (root == null) return "";
        Queue<TreeNode> q =new ArrayDeque<>();
        StringJoiner sj =new StringJoiner(",");
        q.add(root);
        sj.add(Integer.toString(root.val));
        while (!q.isEmpty()){
            TreeNode head = q.remove();
            if (head.left != null){
                q.add(head.left);
                sj.add(Integer.toString(head.left.val));
            }else {
                sj.add("null");
            }
            if (head.right !=null ){
                q.add(head.right);
                sj.add(Integer.toString(head.right.val));
            }else {
                sj.add("null");
            }
        }
        return  sj.toString();
    }
    public  TreeNode deserialize(String data){
        if (data.length()==0) return null;
        String[] nodes =data.split(",");
        Queue<TreeNode> q =new ArrayDeque<>();
        TreeNode root =new TreeNode(Integer.parseInt(nodes[0]));
        q.add(root);
        int idx =1, n=nodes.length;
        while(idx <n){
            //不必以!q.isEmpty()作为判断条件
            TreeNode head = q.remove();
            if (!nodes[idx].equals("null")){
                TreeNode left =new TreeNode(Integer.parseInt(nodes[idx]));
                head.left = left;
                q.add(left);
            }
            idx++;
            if (idx < n && !nodes[idx].equals("null")){
                TreeNode right =new TreeNode(Integer.parseInt(nodes[idx]));
                head.right =right;
                q.add(right);
            }
            idx++;
        }
        return root;
    }
    //前序遍历
    public void leftPrint(TreeNode root){
        if (root !=null ) {
            System.out.println(root.val);
            leftPrint(root.left);
            leftPrint(root.right);
        }else {
            System.out.println("null");
        }
    }

    public  String  se(TreeNode node){
         if (node == null) return "{}";
        Queue<TreeNode> queue =new LinkedList<>();
        queue.add(node);
        StringBuffer sb = new StringBuffer();
        List<Integer> list =new ArrayList<>();
       list.add(node.val);
        while (!queue.isEmpty()){
            TreeNode head = queue.remove();
            if (head.left !=null){
                queue.add(head.left);
                list.add(head.left.val);
            }else {
                list.add(null);
            }
            if (head.right !=null){
                queue.add(head.right);
                list.add(head.right.val);
            }else {
                list.add(null);
            }
        }

        while (list.get(list.size()-1) == null){
            list.remove(list.size()-1);
        }
        for (Integer integer : list) {
            sb.append(integer+",");
        }
        return  sb.toString() ;
    }

    public  TreeNode  de(String A){

        if (A==null ||A=="")return null;
        String[] split = A.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode head = new TreeNode(Integer.parseInt(split[0]));
        queue.add(head);
        int idx =1 , last =split.length;
        while (idx <last){
            TreeNode node = queue.remove();
            //上面是层及遍历，下面就是每个根下挂俩元素
            if (!split[idx].equals("null")){
                TreeNode node1 = new TreeNode(Integer.valueOf(split[idx]));
                node.left =node1;
                queue.add(node1);
            }
            idx++;
            if (idx< last&&!split[idx].equals("null")){
                TreeNode node1 = new TreeNode(Integer.valueOf(split[idx]));
                node.right =node1;
                queue.add(node1);
            }
            idx++;
        }
        return head;

    }
   // 测试用例
   public static void main(String[] args) {
    TreeNode root =new TreeNode(1);
       root.left = new TreeNode(2);
       root.right = new TreeNode(3);
       root.right.left = new TreeNode(4);
       root.right.right = new TreeNode(5);
       Codec codec = new Codec();
       String serialized = codec.se(root);
       System.out.println(serialized);
       System.out.println("-------------------------------");
       TreeNode de = codec.de(serialized);
       codec.leftPrint(de);
   }
}
